//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,1]
//输出：[[0,1],[1,0]]
// 
//
// 示例 3： 
//
// 
//输入：nums = [1]
//输出：[[1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 6 
// -10 <= nums[i] <= 10 
// nums 中的所有整数 互不相同 
// 
//
// Related Topics 数组 回溯 👍 2565 👎 0
import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution46
{
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        func(nums, 0, ret);
        return ret;
    }

    void func(int[] nums, int curr, List<List<Integer>> vessel) {
        if (curr >= nums.length-1) {
            List<Integer> pathRes = copyArray(nums);
            vessel.add(pathRes);
            return;
        }

        for (int i = curr; i < nums.length; i++) {
            swap(nums, i, curr);
            func(nums, curr+1, vessel);
            swap(nums, i, curr);
        }
    }

    List<Integer> copyArray(int[] nums) {
        ArrayList<Integer> pathResult = new ArrayList<>();
        for (int it : nums) {
            pathResult.add(it);
        }

        return pathResult;
    }

    void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
